<?php
/* $Id: Tree.php 181 2010-08-18 01:29:56Z jxd $ */

/*
 *  ********** 使用时请保留此信息 **********
 *  树型结构算法
 *  Author: haijd <haijd.yuiy@gmail.com>
 *  ********** 使用时请保留此信息 **********
 */
class Tree {
    var $data_cache;            //所有节点缓存数据
    var $data_cache_parent;     //所有节点父节点缓存数据
    var $data_sort;             //排序后的数据
    var $data_parent;           //指定节点父节点数据

    var $key_id;                //数据表关键字字段名
    var $key_name;              //名称字段名
    var $key_parent;            //父ID字段名

    var $spacing_fore      = '│';      //有上级时的前间隔符
    var $spacing_fore_none = '　';      //无上级时的前间隔符
    var $spacing_back      = '├';      //有下级时的后间隔符
    var $spacing_back_none = '└';      //无下级时的后间隔符


    /*
     *  初始化函数
     */
    function tree() {
        $this->data_sort   = array();
        $this->data_parent = array();
    }


    /*
     *  设置缓存数据
     *  @param:     $data_array 从数据库中选出来的数据，要求必需求有指定的"关键字"、
     *                          "名称"、"父ID"等字段
     *  @return:    无返回，结果保存在 $this->data_cache 和 $this->data_cache_parent 中
     */
    function set_data_cache(&$data_array) {
        if(is_array($data_array)) {
            foreach($data_array as $data) {
                $this->data_cache[$data[$this->key_parent]][$data[$this->key_id]] = $data;
                $this->data_cache_parent[$data[$this->key_id]][$data[$this->key_parent]] = $data[$this->key_name];
            }
        }
    }


    /*
     *  取得指定节点所有下级节点的 key_id
     *  @param:     $node_id    指定要取的节点ID，默认为根节点
     *  @return:    以","分隔的ID列表
     */
    function get_child_id($node_id='-1'){
        if (isset($this->data_cache[$node_id])){
            foreach($this->data_cache[$node_id] as $child_id => $data) {
                $node_id .= ",".$this->get_child_id($child_id);
            }
        }
        return $node_id;
    }


    /*
     *  取得指定节点ID的父节点
     *  @param:     $node_id    指定要取的节点ID，默认为根节点
     *  @return:    无返回，结果数据保存在 $this->data_parent
     */
    function get_parent_data($node_id){
        if ($node_id != -1 && is_array($this->data_cache_parent[$node_id])){
            foreach($this->data_cache_parent[$node_id] as $parent_id => $parent_data) {
                array_push($this->data_parent, array('id'=>$node_id, 'data'=>$parent_data));
                if($parent_id != '-1') {
                    $this->get_parent_data($parent_id);
                }
            }
        }
    }


    /*
     *  对缓存数据进行排序，以方便生成树形列表
     *  @param: $node_id    指定生成树的节点ID，默认为全部
     *          $expand     是否展开树，若不展开则只显示指定根节点的直属下级节点
     *
     *          $level          程序自用，记录当前位于树的第几层
     *          $queue          程序自用，前间隔符列表
     *          $upper_is_last  程序自用，记录父节点是否为该层中的最后一个节点
     *  @return 无返回，结果保存在 $this->data_sort 中
     */
    function sort_data($node_id="-1", $expand=1, $level=0, $queue='', $upper_is_last='') {
        $data = array();
        if (isset($this->data_cache[$node_id])) {

            #-------------------------------------------------
            # 前/后缀间隔符准备工作 - 1
            $self_quantity = count($this->data_cache[$node_id]);
            $self_count = 0;
            #-------------------------------------------------

            foreach ($this->data_cache[$node_id] as $parent_id => $data_cache) {
                $data = $data_cache;

                #-------------------------------------------------
                # 设置前/后缀间隔符
                $self_count++;

                //设置前缀
                if($level) {
                    $spacing_fore = $queue . ($upper_is_last? $this->spacing_fore_none: $this->spacing_fore);
                } else {
                    $spacing_fore = '';
                }

                //设置后缀
                if($self_quantity == $self_count) {
                    $spacing_back = $this->spacing_back_none;
                    $is_last = 1;
                } else {
                    $spacing_back = $this->spacing_back;
                    $is_last = 0;
                }

                $data['prefix'] = $spacing_fore.$spacing_back;
                #-------------------------------------------------

				//设置当前层级
				$data['level'] = $level + 1;

                #-------------------------------------------------
                # 设置是否有下级数据标志
                $data['lower_level'] = 1;
                if (empty($this->data_cache[$data_cache[$this->key_id]])) {
                    $data['lower_level'] = 0;
                }
                #-------------------------------------------------

                //添加至最终数据项中
                array_push($this->data_sort, $data);

                #-------------------------------------------------
                # 递归取得下级数据
                if ($expand == 1) {
                    $this->sort_data($data_cache[$this->key_id], $expand, $level+1, $spacing_fore, $is_last);
                }
                #-------------------------------------------------

                unset($data);
            }
        }
    }


    /*
     *  生成树形列表式的下拉菜单
     *  @param: $default_id  默认选择的节点ID，默认为根ID
     *          $filter_id   要排除的节点ID
     *          $root_name   设置根节点名称，如不设置则不显示
     *  @return 下拉菜单数据项
	 */
	function get_sort_select($default_id='-1', $filter_id='', $root_name='') {
		$data = $this->get_sort_array($filter_id, $root_name);
		$select = create_select($data, 0, 1, $default_id);
		return $select;
	}

    /*
     *  生成树形列表式的下拉数组
     *  @param: $filter_id  要排除的节点ID
     *          $root_name  设置根节点名称，如不设置则不显示
     *  @return 下拉菜单数据项
     */
    function get_sort_array($filter_id='', $root_name='') {

        //取得要排除分类的所有下级ID
        $filter_array = array();
        if($filter_id) {
			$array = array();
			$arr_tmp = explode(',', $filter_id);
			foreach($arr_tmp as $tmp) {
	            $str = $this->get_child_id($filter_id);
				$array[] = $str;
			}
			$str = implode(',', $array);
            $filter_array = explode(',', $str);
            unset($array, $arr_tmp, $tmp, $str);
        }

        //生成下拉菜单项
        $select_array = array();
        if($root_name) {
            array_push($select_array, array('-1', $root_name));
        }
        foreach($this->data_sort as $data) {
            if(!in_array($data[$this->key_id], $filter_array)) {
                $arr_tmp = array($data[$this->key_id], $data['prefix'].$data[$this->key_name], $data['level']);
                array_push($select_array, $arr_tmp);
            }
        }

        return $select_array;
    }

}

